#include <stdio.h>
int sort_binary_search(int a[], int n, int k)
{
    int retidx = 0;
    int from = 0;
    int to = n-1;
    int m;
    while(1) {
        if(0 == from-to) {
            retidx = k>=a[from]?from+1:from;
            break;
        }

        if(1 == from-to) {
            if(k<a[from]) {
                retidx = from;
            }
            else if(k<a[to]) {
                retidx = to;
            }
            else {
                retidx = to+1;
            }

            break;
        }

        m = from + (to-from)/2 ;
        if(k == a[m]) {
            retidx = m+1;
            while(a[retidx] == k) {
                retidx ++;
            }

            break;
        }
        else if(k>a[m]) {
            from = m + 1;
        }
        else {
            to = m - 1 ;
        }
    }

    return retidx;
}


int sort_binary_search_insert(int a[], int n)
{
    int idx = 0;
    int i;
    int j;
    int k_add;
    for(i=1; i<n; i++) {
        k_add = a[i];
        idx =  sort_binary_search(a, i, k_add);
        
        for(j=i-1; j>=idx; j--) {
            a[j+1] = a[j];
        }

        a[idx] = k_add;
    }

    return 0;
}


void display(int a[], int n)
{
    int i;
    for(i=0; i<n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}


int main()
{
    int a[] = {1,6,2,3,9,7,8,0,4,5,1,6,2,3,9,7,8,0,4,5};
    int n = sizeof(a)/sizeof(a[0]);
    sort_binary_search_insert(a, n);
    display(a, n);

    return 0;
}
